#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1539. 第 k 个缺失的正整数
// 【难度】简单
// 【提交】2025.9.23 https://leetcode.cn/problems/kth-missing-positive-number/submissions/665272586/
// 【标签】二分查找；数组
class Solution_LC1539 {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (arr[0] > k) {
            return k;
        }
        
        int left = 0, right = arr.size();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int missing_count = arr[mid] - mid - 1;
            
            if (missing_count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        int missing_before_left_minus_1 = arr[left - 1] - (left - 1) - 1;
        return arr[left - 1] + (k - missing_before_left_minus_1);
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个严格升序排列的正整数数组arr和一个整数k，找到数组中缺失的第k个正整数。
 * 模型：二分查找，利用数组有序性和缺失数字的规律性。
 * 
 * 二、标准解法状态设计
 * 对于有序数组arr，到位置i为止缺失的数字个数为：arr[i] - i - 1。
 * 使用二分查找找到第一个缺失数字个数≥k的位置，然后计算第k个缺失的数字。
 * 
 * 三、你的实现思路
 * 使用二分查找法，通过比较缺失数字个数与k的关系，确定第k个缺失数字的位置。
 * 特别处理了边界情况（第一个元素就大于k的情况）。
 * 
 * 四、逐行注释（带细节提醒）
 * if (arr[0] > k) { // 如果第一个元素大于k，说明前k个数字都缺失
 *     return k;     // 直接返回k
 * }
 * 
 * int left = 0, right = arr.size(); // 二分查找的左右边界
 * while (left < right) { // 二分查找循环
 *     int mid = left + (right - left) / 2; // 计算中间位置，防止溢出
 *     int missing_count = arr[mid] - mid - 1; // 计算到mid位置为止缺失的数字个数
 *     
 *     if (missing_count >= k) { // 如果缺失个数≥k，说明答案在左侧
 *         right = mid;
 *     } else {                  // 否则在右侧
 *         left = mid + 1;
 *     }
 * }
 * 
 * // 计算在left-1位置之前缺失的数字个数
 * int missing_before_left_minus_1 = arr[left - 1] - (left - 1) - 1;
 * // 第k个缺失数字 = 前一个元素 + 还需要缺失的数字个数
 * return arr[left - 1] + (k - missing_before_left_minus_1);
 * 
 * 五、正确性证明
 * 对于有序数组，到位置i为止缺失的数字个数为arr[i]-i-1，这个值是单调递增的。
 * 二分查找可以正确找到第一个缺失数字个数≥k的位置，然后通过计算得到第k个缺失数字。
 * 
 * 六、复杂度
 * 时间：O(log n)，其中n是数组长度，使用二分查找。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，适用于大规模数据；
 *   - 代码简洁，实现高效；
 *   - 利用了数组有序性，避免了暴力枚举。
 * 缺点：
 *   - 二分查找的边界条件需要仔细处理；
 *   - 对于初学者，理解缺失数字个数的计算可能有一定难度。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (arr.empty()) return k;
 * 2. 使用更明确的变量名（如 targetIndex 代替 left）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么缺失数字个数是arr[i]-i-1；
 * 4. 可以考虑使用更直观的迭代方法，虽然时间复杂度较高但更易理解。
 * 
 * 九、一句话总结
 * 二分查找是解决有序数组中查找缺失数字的高效方法，你的实现准确且优雅，
 * 展现了利用数学规律优化算法效率的能力。
 */